package com.hqq.exercise.tree;

/**
 * ConvertTreeToDList 二叉搜索树与双向链表
 * 题目描述:
 * 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向
 * 样例输入:
 * ---------10
 * -------6    14
 * -----4  8  12 16
 * 样例输出
 * 4<==>6<==>8<==>10<==>12<==>14<==>16
 * 思路:
 * 中序遍历二叉搜索树 遍历到根节点时 把左子树的最右节点next节点指向它 再把它的next节点指向右子树的最左节点
 * Created by heqianqian on 2017/8/15.
 */
public class ConvertTreeToDList {

    public static TreeNode convertTreeToDList(TreeNode root) {
        TreeNode dList = new TreeNode();

        convert(root, dList);
        while (dList != null && dList.left != null) {
            dList = dList.left;
        }
        return dList;
    }

    private static void convert(TreeNode root, TreeNode dList) {
        if (root == null) {
            return;
        }
        TreeNode current = root;
        if (current.left != null) {
            convert(current.left, dList);
        }
        current.left = dList;
        if (dList != null) {
            dList.right = current;
        }
        dList = current;
        if (current.right != null) {
            convert(current.right, dList);
        }
    }
}
